package algorithm_demo.demo05;

/**
 * 暴力递归
 * 汉诺塔问题：2的N次方-1
 * @author Api
 * @date 2023/3/4 22:54
 */
public class Code01_ViolentRecursion {
    /*
     * 暴力递归
     * 暴力递归就是尝试
     * 1.把问题转化为规模缩小了的同类问题的子问题
     * 2.有明确的不需要继续进行递归的条件（base case）
     * 3.有当得到了子问题的结果之后的决策过程
     * 4.不记录每一个子问题的解
     * */


    /*
    * 打印n层汉诺塔从最左边移到最右边的全部过程
    * */

    public static void hanoi2(int n){
        if (n>0){
            func(n, "left", "right", "mid");
        }
    }

    public static void func(int N, String from, String to, String other) {
        if (N == 1) {
            System.out.println("Move 1 from " + from + " to " + to);
        } else {
            func(N - 1, from, other, to);
            System.out.println("Move " + N + " from. " + from + " to " + to);
            func(N-1,other, to, from);
        }
    }

    public static void main(String[] args) {
        int n = 3;
        hanoi2(n);
        System.out.println("========================");
    }
}
